﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//剑指 Offer II 062. 实现前缀树❤️
class Trie {
public:
	//字符串哈希做法
	vector<Trie*> _children;
	bool _isEnd;
	/** Initialize your data structure here. */
	Trie()
		:_children(26, nullptr)
		, _isEnd(false)
	{}
	Trie* searchpre(string prefix)
	{
		Trie* node = this;
		for (auto ch : prefix)
		{
			ch -= 'a';
			if (node->_children[ch] == nullptr)
			{
				return nullptr;
			}
			//找到往下一个字母走
			node = node->_children[ch];
		}
		return node;
	}
	/** Inserts a word into the trie. */
	void insert(string word)
	{
		Trie* node = this;
		for (char ch : word)
		{
			ch -= 'a';
			if (node->_children[ch] == nullptr)//没有就插入
			{
				node->_children[ch] = new Trie();
			}
			node = node->_children[ch];
		}
		node->_isEnd = true;
	}

	/** Returns if the word is in the trie. */
	bool search(string word)
	{
		Trie* node = searchpre(word);
		return node != nullptr && node->_isEnd == true;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		Trie* node = searchpre(prefix);
		return node != nullptr;
	}
};

//剑指 Offer II 063. 替换单词
//字典树哈希
struct Trix
{
	vector<Trix*> _children;
	bool _isEnd;
	Trix()
		:_isEnd(false)
		, _children(26, nullptr)
	{}
	string searchPre(string word, bool& flag)
	{
		string str;
		Trix* node = this;
		for (auto ch : word)
		{
			int n = ch - 'a';
			if (node->_isEnd == true)//找到最短的
			{
				flag = true;
				return str;
			}
			str += ch;
			if (node->_children[n] == nullptr)
			{
				return str;
			}
			node = node->_children[n];
		}
		return str;
	}
	void insertPre(string word)
	{
		Trix* node = this;
		for (auto ch : word)
		{
			ch -= 'a';
			if (node->_children[ch] == nullptr)
			{
				node->_children[ch] = new Trix();
			}
			node = node->_children[ch];
		}
		node->_isEnd = true;
	}
};
class Solution {
public:
	string replaceWords(vector<string>& dictionary, string sentence) {
		Trix tr;
		int n = dictionary.size();
		for (int i = 0; i < n; i++)
		{
			string str = dictionary[i];
			tr.insertPre(str);
		}
		int l = sentence.size();
		int start = 0;
		string ret;
		for (int i = 0; i < l; i++)
		{
			bool flag = false;//判断是否找到
			if (sentence[i] == ' ')
			{
				string s1 = sentence.substr(start, i - start);
				start = i + 1;
				string s2 = tr.searchPre(s1, flag);
				if (flag)
				{
					ret += s2;
					ret += ' ';
				}
				else
				{
					ret += s1;
					ret += ' ';
				}
			}
		}
		//处理最后没有空格的
		bool flag = false;
		string s1 = sentence.substr(start, l - start);
		string s2 = tr.searchPre(s1, flag);
		if (flag)
		{
			ret += s2;
		}
		else
		{
			ret += s1;
		}
		return ret;
	}
};